package com.algorithm.sort;

/**
 * @author msi
 * 选择排序 时间复杂度 O(n^2) 空间复杂度 O(1)
 */
public class SelectionSort {

    public static void main(String[] args) {
        int [] arr = {1,4,2,9,80,6,7,5,-1,56,-20};
        selectionSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+",");
        }
    }

    public static void selectionSort(int[] arr){
        if(arr == null || arr.length <2){
            return;
        }

        //每次选择最小的值并记录index
        for (int i = 0;i < arr.length;i++){
            int min = arr[i];//记录当前循环的最小值
            int j = i;//记录最小值index
            for (int k = i;k<arr.length ; k++){
                if(arr[k] < min){
                    min = arr[k];
                    j = k;
                }
            }
            swap(arr,i,j);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
